package com.zengqingfa.algorithm.leetcode;

import com.zengqingfa.algorithm.PrintUtil;

/**
 *
 * @fileName: LeetCodeTest_88
 * @author: zengqf3
 * @date: 2021-5-25 15:56
 * @description: 88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
 

提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCodeTest_88 {

    /**
     * 合并有序数组-使用第三方数组
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        //创建新数组
        int[] arr = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) {
            if (nums1[i] < nums2[j]) {
                arr[k++] = nums1[i++];
            } else {
                arr[k++] = nums1[j++];
            }
        }
        //如果nums1数组循环完毕
        if (j < n) {
            while (j < n) {
                arr[k++] = nums2[j++];
            }
        }
        //如果nums2数组循环完毕
        if (i < m) {
            while (i < m) {
                arr[k++] = nums1[i++];
            }
        }
        //把arr复制到nums1
        for (int l = 0; l < arr.length; l++) {
            nums1[l] = arr[l];
        }
    }

    /**
     * 合并有序数组-就地（使用o(1)的空间）-使用双指针
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1;
        //nums1从尾向前
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] < nums2[j]) {
                nums1[k--] = nums2[j--];
            } else {
                nums1[k--] = nums1[i--];
            }
        }

        if (j >= 0) {
            while (j >= 0) {
                nums1[k--] = nums2[j--];
            }
        }
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{11, 22, 33, 44, 0, 0, 0};
        int[] nums2 = new int[]{1, 2, 3};
        // merge(nums1, nums1.length - nums2.length, nums2, nums2.length);
        merge2(nums1, nums1.length - nums2.length, nums2, nums2.length);
        PrintUtil.print(nums1);
    }
}
